Program analysis tools are important for understanding program behavior. Computer architects need such tools to evaluate how well programs will perform on a particular architecture. Software writers need such tools to analyze and optimize their programs and identify critical pieces of code. Compiler writers often use such tools to find out how well, for example, their instruction scheduling or branch prediction algorithm is performing or to provide input for profile-driven optimizations.
Conventional program analysis tools may evaluate various program metrics for discovering performance bottlenecks, such as routines and loops that consume the most CPU time, regions of code that spend a significant amount of their CPU time waiting on memory, loops that generate excessive cache misses, uneven distribution of work across threads in parallel regions, lack of effective parallelism in a loop or a routine, etc.
One type of metric that may be collected and evaluated is a call count metric. A call count is the number of times a particular function is called in total in a program or from a particular other function in the program. For example, a program includes three functions A, B, and C. During the execution of the program, the function A calls the function C five times and the function B calls the function C ten times. Thus, the call count for the function C is fifteen.
Function as used herein refers to a set of instructions that compute a value or take an action, such as printing or reading a character value. Functions are also referred to as procedures and subroutines. A program being monitored may include several functions and each function may call other functions or itself. During program optimization, the call count and functions performing the most number of calls may be evaluated to identify areas of code that can be optimized to increase processing efficiency and reduce execution time.
FIG. 6 illustrates calling a function, i.e., a function call, in a program. The function 610 is being executed. The function 610 may be the main function in a C program. Line 10 includes a call instruction which calls the function 620. The called function 620 is executed and includes a return instruction 621 designating the return to the main function 610 in this example.
The conventional technique for collecting a call count is to include special code in the program which records each call as it occurs. For example, most C compilers support a command-line option to insert code including a call to a special function, e.g., mcount( ), which counts each call. This inserted code is typically added at the beginning of each subroutine and is shown as 622 in the beginning of the function 620. The function mcount( ), which is called by the code 622, may increment a counter associated with the source address and/or the source/destination address pair for each return or call instruction.
For example, referring to the function 620, the source address is the address of the return instruction 621, which is executed in this example to return to the main function 610. The destination address is the address of the next line to be executed, which may be line 11 in the function 610. By monitoring the source and destination addresses, the call count as well as a function making a call counted in the call count can be determined. Conventional program analysis tools may add the code 622 when the program is initially being compiled, at link-time, or dynamically at runtime via code patching.
All of these conventional programming analysis tools have in common the requirement of adding code, such as the code 622, to a program to determine a call count. However, adding the code 622, even if done automatically by a compiler, may affect the proper operation of the program being monitored. Furthermore, special privileges required for adding code to the program may not be available, and the additional code 622 increases execution time of the program.